package Z代码随想录.数组;

public class Leetcode977 {
    // 有序数组的平方
    // 该题用常规思想，就是遍历数组，把每一个元素平方，最后整体排序，这样时间复杂度会最快 也会达到 O(n+nlogn)
    // 数组中是按非递减顺序，从负数到正数，所以平方后的最大值，只可能出现在两侧位置
    // 所以此处我们考虑使用双指针法，一个在 0 下标位置， 一个在 nums.length-1 位置
    // 通过比较 最左边的平方值和最右边的平方值，谁大，就放入一个新的数组中的末尾，
    // 如果左边大,就放入新数组的末尾位置，并且新数组下标往前挪一个，左边下标++
    // 如果右边大，就放入到新数组末尾位置，并且新数组下标往前挪一个，右边下标--

    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        int left = 0;  // 左指针
        int right = nums.length - 1;  // 右指针
        int index = nums.length - 1;
        while (left <= right){
            if (nums[left] * nums[left] > nums[right] * nums[right]){
                ans[index--] = nums[left] * nums[left];
                left++;
            }else {  // 此时当 left<=right时候，最后一个数的时候，就进入这个else条件
                ans[index--] = nums[right] * nums[right];
                right--;
            }
        }
        // 最后返回 ans 数组
        return ans;
    }
}
